package class_0910AVLTrees;


/**
 * AVL树是一个高度平衡的二叉搜索树， 每个节点的高度差至多为1.
 * 每个节点x， 维护一个bf = abs(rightHeight - leftHeight);
 * 然后是旋转操作， 在红黑树那块已经处理了。
 * @param <K>
 * @param <V>
 */
public class AVLTree<K extends Comparable<K>,V> {
    /**
     * def bf = RH - LH
     * @param <K>
     * @param <V>
     */
    public static class Node<K extends Comparable<K>,V>{
        private K key;
        private V value;
        private Node<K,V> left;
        private Node<K,V> right;
        private Node<K,V> p;
        private int bf; // 平衡因子
        public Node(K key, V value){
            this.key = key;
            this.value = value;
            this.bf = 0;
        }
        public K getKey(){
            return key;
        }
        public V getValue(){
            return value;
        }
        public V setValue(V value){
            V ret = this.value;
            this.value = value;
            return ret;
        }
    }
    private Node<K,V> root;

    public AVLTree(){
        root = null;
    }

    private static <K extends Comparable<K>,V>void leftRotate(AVLTree<K, V> avl, Node<K, V> node){
        Node<K, V> curR = node.right;
        node.right = curR.left;
        if(curR.left != null) {
            curR.left.p = curR;
        }
        curR.p = node.p;
        if(node.p==null){
            avl.root = curR;
        }
        else if(node == node.p.left){
            node.p.left = curR;
        }
        else{
            /// node == node.p.right
            node.p.right = curR;
        }
        curR.left = node;
        node.p = curR;

    }

    private static <K extends Comparable<K>, V> void rightRotate(AVLTree<K, V> avl, Node<K, V> node){
        Node<K, V> curL = node.left;
        node.left = curL.right;
        if(curL.right!=null){
            curL.right.p = curL;
        }
        curL.p = node.p;
        if(node.p==null){
            avl.root = curL;
        }
        else if(node == node.p.left){
            node.p.left = curL;
        }
        curL.right = node;
        node.p = curL;
    }
    public boolean contains(K key){

        return search(key)!=null;
    }
    public Node<K,V> search(K key){
        Node<K,V> cur = root;
        while(cur!=null){
            if(cur.key.compareTo(key) < 0){
                cur = cur.right;
            }
            else if(cur.key.compareTo(key) > 0){
                cur = cur.left;
            }
            else{
                //cur.key.equals(key)
                return cur;
            }
        }
        return null;
    }
    public void insert(K key, V value){
        Node<K,V> p = null;
        Node<K,V> cur = root;
        while(cur!=null){
            p = cur;
            if(cur.key.compareTo(key) < 0){
                cur = cur.right;
            }
            else if (cur.key.compareTo(key) > 0){
                cur = cur.left;
            }
            else{
                cur.value = value; //更新值
                return ;
            }
        }
        Node<K,V> node = new Node<K, V>(key,value);
        node.p = p;
        if(p==null){
            this.root = node;
        }
        else if(p.key.compareTo(key)<0){
            p.right = node;
        }
        else{
            // p.key.compareTo(key) > 0
            p.left = node;
        }
        siftUp(this, node);
    }

    private static <K extends Comparable<K>, V> void siftUp(AVLTree<K,V> avl, Node<K,V> node) {
        while(node.p!=null) {
            if (node.p.right == node) {
                node.p.bf++;
            } else {
                //node.p.left == node
                node.p.bf--;
            }
            node = node.p;
            if(node.bf == 2){
                //右高左旋
                AVLTree.leftRotate(avl, node);
                node.bf-=2;
                node.p.bf--;
                node = node.p;
            }
            else if(node.bf == -2){
                AVLTree.rightRotate(avl, node);
                node.bf+=2;
                node.p.bf++;
                node = node.p;
            }
        }
    }
}
